package dp;

/**
 * @author pengfei.hpf
 * @date 2020/3/1
 * @verdion 1.0.0
 * 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
 *
 * 示例:
 *
 * 输入:
 *
 * 1 0 1 0 0
 * 1 0 1 1 1
 * 1 1 1 1 1
 * 1 0 0 1 0
 *
 * 输出: 4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximal-square
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MaximalSquare {

    public int maximalSquare(char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return 0;
        }
        int maxEdge = 0;
        for(int i = 0; i < matrix.length; i ++){
            for(int j = 0; j < matrix[0].length; j ++){
                if(matrix[i][j] == '1'){
                    int edge = 1;
                    if(i > 0 && j >0){
                        edge = matrix[i-1][j-1] - '0';

                        while(edge >= 1){
                            if(isAllone(matrix, i, j, edge)){
                                break;
                            }
                            edge --;
                        }

                        edge = edge + 1;
                        matrix[i][j] = (char)(edge + '0');
                    }
                    if(edge > maxEdge){
                        maxEdge = edge;
                    }
                }
            }
        }
        return maxEdge * maxEdge;
    }

    private boolean isAllone(char[][] matrix, int i, int j, int edge){
        for(int row = i - edge; row < i; row ++){
            if(matrix[row][j] == '0'){
                return false;
            }
        }
        for(int col = j - edge; col < j; col ++){
            if(matrix[i][col] == '0'){
                return false;
            }
        }
        return true;
    }

    //dp
    public int maximalSquareDp(char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return 0;
        }
        int maxEdge = 0;
        for(int i = 0; i < matrix.length; i ++){
            for(int j = 0; j < matrix[0].length; j ++){
                if(matrix[i][j] == '1'){
                    int edge = 1;
                    if(i > 0 && j >0){
                        edge = Math.min(matrix[i-1][j-1] - '0', matrix[i-1][j] - '0');
                        edge = Math.min(edge, matrix[i][j - 1] - '0');
                        edge = edge + 1;
                        matrix[i][j] = (char)(edge + '0');
                    }
                    if(edge > maxEdge){
                        maxEdge = edge;
                    }
                }
            }
        }
        return maxEdge * maxEdge;
    }

    public static void main(String[] args){

    }
}
